package formal.tree.bst;

import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-01-22 21:07
 */
public class M_230 {
    public static void main(String[] args) {

    }

    public static int count = 0;
    public static int minVal = 0;

    /**
     * 不会-看了大神的才知道-中序遍历的顺序就是二叉查找树从小到大的顺序啊
     * @param root
     * @param k
     * @return
     */
    public static int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return minVal;
    }

    public static void inOrder(TreeNode root,int k){
        if (root==null){
            return;
        }
        inOrder(root.left, k);
        count++;
        if (count==k){
            minVal=root.val;
            return;
        }
        inOrder(root.right,k);

    }

    /**
     * 官方-迭代-中序遍历的变体
     * @param root
     * @param k
     * @return
     */
    public static int kthSmallest2(TreeNode root,int k){
        Stack<TreeNode> stack = new Stack<>();
        int count =0;
        while (true){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            TreeNode pop = stack.pop();
            count++;
            if (count==k){
                return pop.val;
            }
            root=pop.right;
        }
    }
}
